Design sizes are continually expanding, and the task of producing a large, high performance circuit has been getting progressively more difficult. By using hierarchy, and breaking a large design into many smaller macro blocks, handling a complex project becomes somewhat more tractable. With modern chips, however, the number of blocks is now becoming unmanageable; the placement and routing of million-block designs has been identified by the industry as an important research area [15].
The optimization of placement of logical component blocks in a complex semiconductor design is difficult. The problem approaches NP completeness, and therefore the complexity of a brute force enumeration increases exponentially as the number of blocks increases. Therefore, using such an approach becomes untenable except for trivial-sized problems.
A generalized treatment of optimization technologies is provided in Tsaggouris, George, and Zaroliagis, Christos, “A Compendium of Large-Scale Network Optimisation Problems”, Project Number 001907, DELIS Dynamically Evolving, Large-scale Information Systems, Integrated Project, Member of the FET Proactive Initiative Complex Systems, Deliverable D3.4.3, Initial Experimental Studies of Selected Problems (January 2006), expressly incorporated herein by reference.
Dynamic programming is also well known; for some problems, exponentially large portions of the solution space can be eliminated. If available, this provides a way to derive solutions in reasonable amounts of time. The number of problems in which this solution is available is limited—and finding such a proof is frequently difficult.
Greedy algorithms are also well known: at each step of the algorithm, a single decision is made, and the decision is based on what appears to be “best” at that stage, dependent on the limited information known at the time the decision must be committed. This approach has low run times, but produces suboptimal results in most cases.
Placement techniques have been evolving for many years; leading methods include simulated annealing, analytic methods, and recursive bisection.
Methods used for placement vary somewhat based on the size of the problem, and the nature of the objects being placed. If a design is relatively small, annealing methods can produce excellent results; many commercial tools apply annealing for local optimization, and hybrids of annealing and bisection are common.
For larger designs, analytic methods and recursive bisection both perform well; there is a clear preference for analytic placers in industrial settings. Analytic placement, and some forms of recursive bisection, require a “legalization step.” Rough positions for logic elements are determined, and then exact (non-overlapping) locations are obtained as a post-processing step.
If all logic elements are of equal size or at least equal height (FIGS. 1(a) and (b)), making the design “fit” into the space available is trivial. The “standard cell” model, a cornerstone of modern design, allows for varying width, but uniform height.
When logic elements are of uniform height, many powerful local optimization techniques become available. Most placement tools perform branch-and-bound optimization of cell positions [6]. There are also methods to find optimal spacing of cells within a row [5].
For mixed size design, FIG. 1(c), we have a “boulders and dust” problem which contains both standard cells and macro blocks. For many years, this was viewed as an extremely difficult problem; in the past few years, however, great strides have been made. The recursive bisection based tool feng shui [3], and the analytic placement tools APlace [10] and UPlace [4] perform well, by first computing a non-legal abstract placement, and then performing placement legalization. feng shui and APlace both use a mixed-size Tetris legalization method. The “floorplacer” Capo [1] uses a recursive bisection framework integrated with a floorplanner. Placement legality is ensured throughout the flow.
While analytic and bisection methods are common in standard cell and mixed size design, annealing methods have dominated floorplanning. With blocks of varying width and height, it has been essential to approach the problem as one of “packing.” Placement representations such as sequence pair [13] and B*-trees [7] are widely used, with an annealer being used to search the solution space.
Evaluating any particular configuration can be expensive; exchanging the positions of two blocks may disrupt an entire floorplan. Annealers can produce excellent results when given enough run time; unfortunately, the high cost of evaluating a floorplan, coupled with the size of the solution space, makes traditional methods impractical for extremely large problems.
To handle larger designs, a “floorplacement” methodology has been proposed. The placement tool PATOMA [8] performs recursive bisection, but adds a fast “legality checker” to ensure that bisection will not result in a configuration that cannot be legalized easily. PATOMA makes good use of soft macro blocks to gain greater freedom during bisection. The tool Capo [1] also utilizes a bisection framework. Capo has evolved over the years, transitioning from standard cell problems, to mixed size, and recently into floorplacement, through the integration of an annealing based floorplanner. Capo uses bisection when circuit elements are small, but switches to floorplanning when a portion of the placement contains blocks that cannot be legalized easily.
Traditional “flat” floorplanners have difficulty in scaling to handle very large designs, particularly when there are many soft macro blocks. Floorplacers handle large problems with soft blocks reasonably well.
While there has been research performed on the floorplanning of L-shaped and T-shaped blocks (shown in FIG. 1(e)), this is seldom used in industry settings. Floorplanning these shapes is fundamentally more difficult than floorplanning rectangles; the typical industry design flow avoids these shapes when possible.